package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/next-greater-node-in-linked-list/description/
 *
 * 给定一个长度为 n 的链表 head
 *
 * 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
 *
 * 返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
 *
 *
 *
 * @author hanjuntao
 * @date 2025/8/15 0015
 */
public class L_1019_链表中下一个最大节点 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(5);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        int[] ints = nextLargerNodes3(node1);
        System.out.println(Arrays.toString(ints)); // 550

        // 1,2,7,2,4,5
        ListNode node11 = new ListNode(1);
        ListNode node12 = new ListNode(7);
        ListNode node13 = new ListNode(5);
        ListNode node14 = new ListNode(1);
        ListNode node15 = new ListNode(9);
        ListNode node16 = new ListNode(2);
        ListNode node17 = new ListNode(5);
        ListNode node18 = new ListNode(1);
        node11.next = node12;
        node12.next = node13;
        node13.next = node14;
        node14.next = node15;
        node15.next = node16;
        node16.next = node17;
        node17.next = node18;
        int[] ints2 = nextLargerNodes2(node11);
        System.out.println(Arrays.toString(ints2));

        // [1,7,5,1,9,2,5,1] -> [7,9,9,9,0,5,0,0]
    }

    /**
     * 思路：
     *
     * 暴力解法
     * 暴力的做法，是固定当前值不动，再开一个指针去往后找较大的值，找到了，就将当前位置更新为找到的那个值，否则则为0。
     *
     * @param head
     * @return
     */
    public static int[] nextLargerNodes(ListNode head) {
        List<Integer> list = new ArrayList<>();

        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;

            boolean flag = false;
            while (next != null) {
                if (next.val > curr.val) {
                    list.add(next.val);
                    flag = true;
                    break;
                }

                next = next.next;
            }

            if (!flag) {
                list.add(0);
            }

            curr = curr.next;
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    public static int[] nextLargerNodes3(ListNode head) {
        List<Integer> list = new ArrayList<>();

        ListNode curr = head;
        while (curr != null) {
            list.add(curr.val);
            curr = curr.next;
        }

        int[] res = new int[list.size()];
        Stack<Integer> stack = new Stack<>();

        for (int j = 0; j < list.size(); j++) {
            while (!stack.empty() && list.get(stack.peek()) < list.get(j)) {
                int index = stack.pop();
                res[index] = list.get(j);
            }

            stack.push(j);
        }

        return res;
    }

    /**
     * 思考：
     *
     * 下一个更大的值的问题核心：
     * 在检测到下一个更大值的时候，如何更新当前值。
     *
     * 暴力的做法，是固定当前值不动，再开一个指针去往后找较大的值，找到了，就将当前位置更新为找到的那个值，否则则为0。
     *
     * 可以换个思路，依次将元素入栈，如果检测到栈内的元素值比当前值小，
     * 则将栈顶元素出栈，并更新当前位置的值为栈顶元素对应的值，直至栈为空或者栈顶元素比当前值大。
     *
     * @param head
     * @return
     */
    public static int[] nextLargerNodes2(ListNode head) {
        List<Integer> list = new ArrayList<>();
        //链表元素存储到集合中
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        //栈中存储的是元素的下标，并且从栈底到栈顶元素在集合中对应的
        //值是从大到小的
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            while (!stack.empty() && list.get(stack.peek()) < list.get(i)) {
                //如果栈顶元素对应的值小于当前值，说明栈顶元素遇到了比他小的
                int index = stack.pop();
                System.out.println("当前值：" + list.get(i) + " 弹出栈顶 index:" + index + " value:" + list.get(index));
                System.out.println("当前值：" + list.get(i) + " res赋值 index:" + index + " value:" + list.get(index));
                res[index] = list.get(i);
            }
            stack.push(i);
            System.out.println("入栈 index:" + i + " value:" + list.get(i));
        }
        return res;
    }
}
